package com.yun.algorithmproblem.leetcode;

import java.util.*;

/**
 * 2065. 最大化一张图中的路径价值
 * 给你一张 无向 图，图中有 n 个节点，节点编号从 0 到 n - 1 （都包括）。同时给你一个下标从 0 开始的整数数组 values ，其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开始的二维整数数组 edges ，其中 edges[j] = [uj, vj, timej] 表示节点 uj 和 vj 之间有一条需要 timej 秒才能通过的无向边。最后，给你一个整数 maxTime 。
 * <p>
 * 合法路径 指的是图中任意一条从节点 0 开始，最终回到节点 0 ，且花费的总时间 不超过 maxTime 秒的一条路径。你可以访问一个节点任意次。一条合法路径的 价值 定义为路径中 不同节点 的价值 之和 （每个节点的价值 至多 算入价值总和中一次）。
 * <p>
 * 请你返回一条合法路径的 最大 价值。
 * <p>
 * 注意：每个节点 至多 有 四条 边与之相连。
 */
public class Leetcode2065 {
    public static void main(String[] args) {
        int[] values = {0, 32, 10, 43};
        int[][] edges = {{0, 1, 10}, {1, 2, 15}, {0, 3, 10}};
//        int[] values={1,2,3,4,};
//        int[][] edges={{0,1,10},{1,2,11},{2,3,12},{1,3,13}};
        int maxTime = 49;
        Leetcode2065 obj = new Leetcode2065();
        int max = obj.maximalPathQuality(values, edges, maxTime);
        System.out.println(max);
    }

    int ans=0;
    int[] values;
    int maxTime;
    List<int []>[] g;
    boolean[] visited;

    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        this.values=values;
        this.maxTime=maxTime;
        int n = values.length;
        g=new ArrayList[n];
        // 正确初始化每个元素为新的 ArrayList 对象
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            int x=e[0];
            int y=e[1];
            int time=e[2];
            g[x].add(new int[]{y,time});
            g[y].add(new int[]{x,time});
        }
        visited=new boolean[n];
        visited[0]=true;
        dfs(0,0,values[0]);
        return ans;
    }

    //Dijkstra算法 -- 返回一个数组,存储的是每个位置到0位置的最短距离
    private int[] dijkstra(List<int []>[] g,int n){
        int[] dist=new int[n];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[0]=0;
        /*
          queue中的数组,[0]代表当前节点,[1]代表当前节点距离起始节点的距离
         */
        PriorityQueue<int[]> queue=new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        queue.add(new int[]{0,0});
        while (!queue.isEmpty()){
            int[] current = queue.poll();
            int currentNode=current[0];
            int currentDist=current[1];
            for (int[] next : g[currentNode]) {
                int nextNode=next[0];
                int costDist=next[1];
                int nextDist=currentDist+costDist;
                if(nextDist<dist[nextNode]){
                    dist[nextNode]=nextDist;
                    queue.add(new int[]{nextNode,nextDist});
                }
            }
        }
        return dist;
    }

    private void dfs(int n,int time,int value){
        if(n==0){
            if(value>ans){
                ans=value;
            }
        }
        for (int[] next : g[n]) {
            if(time+next[1]>maxTime){
                continue;
            }
            if(!visited[n]){
                visited[n]=true;
                dfs(next[0],time+next[1],value+values[n]);
                visited[n]=false;
            }else {
                dfs(next[0],time+next[1],value);
            }
        }
    }
}

